#!/usr/bin/python
# Filename: BTree.py

# binary tree

# conceptions:
# node, root, child, left child, right child, parent,
# branch, leaf,
# edge, path, lengh of path, ancestor(ascendence), descendence,
# degree of node, degree of tree,
# depth(max(level)), height(max(level) +1), level of node(start from 0), width,

# full b-tree: every node, either is a leaf or has 2 children

# complete b-tree: if the max level is not full, the max-1 level is full,
# and leafs in the max level are all collected on the left part; or the max level is full.

# extended b-tree: add leaf as child to every possible node
# 1) after externsion, the tree becomes full, and added leaf = original node + 1
# prove(induction):
# when add child to tree, it's degree +1.
# tree of root(1 node) has degree of 2 = 1+1, so tree of n nodes has n+1 degree.
# when extending, add count of degree leafs to the tree, that is n+1 = node+1.
# 2) extended path length E, internal path length I, E = I + 2n
# prove(induction):
# when tree of root(1 node), E = 2, I = 0, E = I + 2*1 is obviously true.
# assume that when tree of n nodes, E(n) = I(n) + 2n is true.
# when add a leaf(n+1), after extension, delete the original leaf which length of path is k.
# I(n) = I(n+1) - k, E(n) = E(n+1) -2(k+1) + k = E(n+1) -k - 2,
# -> E(n+1) = E(n)+k+2 = I(n)+2n+k+2 = I(n+1)+2n+2 = I(n+1) + 2(n+1).

# property of b-tree
# 0) n = e + 1
# 1) full b-tree theorem: leaf = branch + 1, proved before.
# n = l + b, n-1 = 2b(full b-tree, 2b edge, every n except root(n-1) has an edge linked with its parent)
# -> l + b = 2b + 1 -> l = b + 1
# 2) inference from full b-tree theorem:
# a non-empty b-tree's None reference = node + 1
# 3) any b-tree, 0-degree nodes = 2-degree nodes + 1
# prove(induction):
# when tree of root(1 node), it's obviously true.
# assume that when tree of nodes, it's true.
# when add a leaf:
# a) add to a branch: 0-degree nodes += 1, 2-degree nodes += 1
# b) add to a leaf: 0-degree nodes keep, 2-degree nodes + 1 - 1
# complete.
# or:
# n = n0 + n1 + n2, n = e + 1
# e = n1 + 2*n2 -> n = n1 + 2*n2 + 1
# -> n0 = n2 + 1
# 4) in level j, there are at most 2^j nodes
# 5) in k-height b-tree, there are at most 2^k -1 nodes
# 6) height of n-node complete b-tree is upper[log(2)(n+1)]


class BTreeNode:
    '''Node of Binary Tree'''
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def __str__(self):
        return (str(self.value))


class BTree:
    '''Binary Tree'''
    def __init__(self, root=None):
        # here's a limitation:
        # value of root can not be a reference towards other BTreeNode
        if root == None:
            self.root = root
        elif type(root) == type(BTreeNode(0)):
            self.root == root
        else:
            self.root = BTreeNode(root)

    def is_empty(self):
        return self.root == None

    def clear(self):
        def delete_tree(root):
            if root != None:
                delete_tree(root.left)
                delete_tree(root.right)
                # "del root" can only delete a reference of root object.
                # bcz it has other reference(root out of the recursion),
                # the real object will not be automatically deleted.
                # so we manually delete it's value, left and right
                del root.value
                del root.left
                del root.right
        delete_tree(self.root)
        # with the same reason above, manually delete it.
        # 1) will it lead to automatically delete all child items?
        # 2) what will happen if there's other reference = root,
        # or any nodes in the original tree.
        # the answer is that reference will be kept,
        # but only the reference, value is manually deleted.
        # 3) how to "real" delete an object
        del self.root
        self.root = None

    def parent(self, node):
        pass

    def left_sibling(self, node):
        pass

    def right_sibling(self, node):
        pass

    def recreate(self, value, left=None, right=None):
        self.clear()
        self.root = BTreeNode(value)
        if left:
            self.root.left = left.root
        if right:
            self.root.right = right.root

def print_self(i):
    print i,

def postorder(root, cmd=print_self):
    '''tree.root is passed into this function, cmd is to deal with nodes'''
    if root:
        postorder(root.left)
        postorder(root.right)
        cmd(root)

def inorder(root, cmd=print_self):
    if root:
        inorder(root.left)
        cmd(root)
        inorder(root.right)

def preorder(root, cmd=print_self):
    if root:
        cmd(root)
        preorder(root.left)
        preorder(root.right)

def level_order(root, cmd=print_self):
    if root == None: return
    '''level order traversal can be also called as width first traversal'''
    # queue is used
    from Queue import Queue
    q = Queue()
    q.en_queue(root)
    while not q.is_empty():
        n = q.de_queue()
        cmd(n.value)
        if n.left:
            q.en_queue(n.left)
        if n.right:
            q.en_queue(n.right)
    del q

def print_tree_indented(root, level=0):
    if root:
        print_tree_indented(root.right, level+1)
        print '  '*level + str(root)
        print_tree_indented(root.left, level+1)

def postorder_incursive(root, cmd=print_self):
    if root == None: return
    # self-defined stack support different types in same stack
    # but in C/C++ stack, a PH must be added to hint how to deal with stack items
    # in this situation, a popped item may need re-push into stack with different PH
    # for example, in post-order traversal:
    # an item poped with non-dealed PH will lead to push this item with left-dealed PH
    # and push its left child with non_dealed PH.
    # an item poped with left-dealed PH will lead to push this item with right-dealed PH
    # and push its right child with non_dealed PH.
    # an item poped with right-dealed PH will just be dealed with its value.
    from Stack import Stack
    s = Stack()
    s.push(root)
    while not s.is_empty():
        n = s.pop()
        if type(n) != type(BTreeNode(0)): cmd(n)
        else:
            s.push(n.value)
            if n.right:
                s.push(n.right)
            if n.left:
                s.push(n.left)
    del s


class SCBTree:
    '''Sequential Completed Binary Tree'''
    # 0, 1, 2, 3, 4, 5, 6, ...
    # 0
    # 1, 2
    # 3, 4, 5, 6
    # 7, 8, 9, 10, 11, 12, 13, 14
    def __init__(self, root=None):
        self.items = []
        if root != None: self.items.append(root)
    
    def __str__(self):
        return str(self.items)

    def left_child(self, pos):
        '''return position of left child of pos'''
        if 2*pos+1 < len(self.items): return 2*pos+1
        else: return -1

    def right_child(self, pos):
        if 2*(pos+1) < len(self.items): return 2*(pos+1)
        else: return -1

    def parent(self, pos):
        if (pos-1)/2 > 0: return (pos-1)/2
        else: return -1

    def left_brother(self, pos):
        if pos > 0 and pos%2==0: return pos -1
        else: return -1

    def right_brother(self, pos):
        if pos > 0 and pos%2==1 and pos+1 < len(self.items): return pos+1
        else: return -1


class BSTree:
    '''Binary Search Tree'''
    # assumption:
    # values in left child are smaller than value
    # values in right child are bigger than value
    # if insert a exist value, return False
    def __init__(self, value=None):
        if value == None: self.root = None
        else: self.root = BTreeNode(value)
        
    def insert(self, value):
        if self.root == None:
            self.__init__(value)
            return True
        curr_node = self.root
        while curr_node:
            print curr_node,
            if curr_node.value == value: return False
            elif value < curr_node.value:
                if curr_node.left != None:
                    curr_node = curr_node.left
                else:
                    curr_node.left = BTreeNode(value)
                    return True
            else:
                if curr_node.right != None:
                    curr_node = curr_node.right
                else:
                    curr_node.right = BTreeNode(value)
                    return True

    def get_parent(self, value):
        '''return a tuple (parent's reference, which child), 
        when value is not found, return (None, None),
        when value is found on root, return (None, 'o')'''
        if self.root == None: return (None, None)
        if self.root.value == value: return (None, 'o')
        curr_node = self.root
        while curr_node:
            if value < curr_node.value:
                if curr_node.left != None:
                    if curr_node.left.value == value: return (curr_node, 'l')
                    else: curr_node = curr_node.left
                else:
                    return (None, None)
            else:
                if curr_node.right != None:
                    if curr_node.right.value == value: return(curr_node, 'r')
                    else: curr_node = curr_node.right
                else:
                    return (None, None)

    def delete(self, value):
        p = self.get_parent(value)
        if p[0] == None and p[1] == None: return False
        # following procedure can be "get_node(value)"
        # "exec" will help to reduce line of code, but it can only be used in python
        if p[1] == 'o':
            c = self.root
        elif p[1] == 'l':
            c = p[0].left
        else:
            c = p[0].right
        l = c.left
        r = c.right
        if l == None:
            # l == None and r == None is in this pattern
            if p[1] == 'o': self.root = r
            elif p[1] == 'l': p[0].left = r
            else: p[0].right = r
        elif r == None:
            if p[1] == 'o': self.root = l
            elif p[1] == 'l': p[0].right = l
            else: p[0].right = l
        else:
            # this algorithm is improved for reduce tree height,
            # or else just move r to right child of l is ok.
            # find max of l
            pptr = None
            ptr = l
            while ptr.right != None:
                pptr = ptr
                ptr = ptr.right
            if pptr == None: #when l.value is the max of tree(l)
                if p[1] == 'o': self.root = l
                elif p[1] == 'l': p[0].left = l
                else: p[0].right = l
            else:
                pptr.right = ptr.left
                ptr.left = l
                if p[1] == 'o': self.root = ptr
                elif p[1] == 'l': p[0].left = ptr
                else: p[0].right = ptr
            ptr.right = r
        del c

    def find_smaller(self, value):
        # ex_Intro_4_4
        # assumption: left child is smaller than right child
        # in in-recursive algorithm, what's in stack belongs to two operations:
        # 1) add value to returned values' list, of course the list is initiate out of the loop
        # 2) root of tree
        # caution: they are all operations.
        # if 1): do add
        # else:
        #   if root = none: nop
        #   elif root.value >= value: push(root.left)
        #   else: push(root.right), push(add(root.value)), push(root.left)
        def get_smaller(value, root):
            if root == None: return []
            elif root.value >= value: return get_smaller(value, root.left)
            else: return get_smaller(value, root.left) + [root.value] + get_smaller(value, root.right)

        return get_smaller(value, self.root)

if __name__ == "__main__":

    def test_btree():
        print "BTree is under testing..."
        bt = BTree(2)
        bt.root.left = BTreeNode(1)
        bt.root.right = BTreeNode(3)
        postorder(bt.root)
        print
        inorder(bt.root)
        print
        preorder(bt.root)
        print
        print_tree_indented(bt.root)
        postorder_incursive(bt.root)
        print
        level_order(bt.root)
        print

        t = bt.root
        bt.clear()
        print bt.root
        # t != None, but has a same reference to an object with original bt.root
        # when del bt.root and change it to root, the object isn't destroied,
        # bcz there's a reference t. but it's value and child are destroied.
        # so following statements will cause error
        #if not t == None:
        #    print t
        # print bt.root.left will cause an error

    def test_bstree():
        bst = BSTree()
        print "bst.insert(2):", bst.insert(2)
        print "bst.insert(3):", bst.insert(3)
        print "bst.insert(1):", bst.insert(1)
        print "bst.insert(5):", bst.insert(5)
        print "bst.insert(4):", bst.insert(4)
        print "inorder(bst.root):", inorder(bst.root)
        print "print_tree_indented(bst.root):"
        print_tree_indented(bst.root)
        print "bst.insert(5):", bst.insert(5)
        print "bst.insert(4):", bst.insert(4)
        print "inorder(bst.root):", inorder(bst.root)
        print "level_order(bst.root):", level_order(bst.root)
        print "bst.find_smaller(3):", bst.find_smaller(3)
        print "bst.find_smaller(10):", bst.find_smaller(10)

        #p = bst.get_parent(3)
        #if p[1] == 'l':
        #    print p[0].left.value
        #elif p[1] == 'r':
        #    print p[0].right.value
        #elif p[1] == 'o':
        #    print bst.root.value
        #else:
        #    print "value not found"

    #test_btree()
    test_bstree()
